import java.util.*;

/**
* @description: 剑指 Offer 60. n个骰子的点数
* @author hewei
* @date 2022/7/23 14:38
* @version 1.0
*/

public class DicesProbability {

    public static void main(String[] args) {
        DicesProbability dicesProbability = new DicesProbability();
        System.out.println(Arrays.toString(dicesProbability.dicesProbability(2)));
    }

    int sum = 0;
    int n;
    HashMap<Integer, Integer> map;
    public double[] dicesProbability1(int n) {
        this.n = n;
        map = new HashMap<>();
        process(1);
        int count = (int) Math.pow(6, n);
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            list.add(entry.getKey());
        }
        Collections.sort(list);
        double[] ans = new double[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = map.get(list.get(i)) / (double) count;
        }
        return ans;
    }

    public void process(int i) {
        if (i > n) {
            map.put(sum, map.getOrDefault(sum, 0) + 1);
            return;
        }
        for (int j = 1; j < 7; j++) {
            sum += j;
            process(i + 1);
            sum -= j;
        }
    }

    public double[] dicesProbability2(int n) {
        double count = Math.pow(6, n);
        int temp = n * 6 - n + 1;
        double[] ans = new double[temp];
        int index = 0;
        for (int i = n; i <= n * 6; i++) {
            ans[index++] = dfs(i, n) / count;
        }
        return ans;
    }

    public int dfs(int target, int n) {
        if (target == 0 && n == 0) return 1;
        if (target - n * 6 > 0 || target - n < 0) return 0;
        int res = 0;
        for (int j = 1; j < 7; j++) {
            if (target - j >= 0) res += dfs(target - j, n - 1);
        }
        return res;
    }

    public double[] dicesProbability3(int n) {
        int count = n * 6 - n + 1;
        double temp = Math.pow(6, n);
        int[][] dp = new int[n][count];
        double[] ans = new double[count];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < 6; i++) {
            dp[0][i] = 1;
        }
        ans[0] = 1 / temp;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < ((i + 1) * 6) - i; j++) {
                for (int k = 1; k < 7; k++) {
                    dp[i][j] += j + 1 - k >= 0 && i - 1 >= 0 ? dp[i - 1][j + 1 - k] : 0;
                }
                if (i == n - 1) ans[j] = dp[i][j] / temp;
            }
        }
        return ans;
    }

    public double[] dicesProbability(int n) {
        int[][] dp = new int[n + 1][6 * n + 1];
        for (int i = 1; i < 7; i++) {
            dp[1][i] = 1;
        }
        double temp = Math.pow(6, n);
        double[] ans = new double[n * 5 + 1];
        for (int i = 1; i < dp.length; i++) {
            for (int j = i; j < 6 * i + 1; j++) {
                for (int k = 1; k < 7; k++) {
                    dp[i][j] += j - k >= 0 ? dp[i - 1][j - k] : 0;
                }
                if (i == n) ans[j - i] = dp[i][j] / temp;
            }
        }
        return ans;
    }
}
